class Node:
    def __init__(self, value):
        self.val = value
        self.neighbors = {}
        self.flag = 0


class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        word_set = set(words)
        tree = Node('#')
        words.sort(key=lambda x: (len(x), x))
        out = []

        def search(node, word):
            for i in range(len(word)):
                if word[i] in node.neighbors:
                    node = node.neighbors[word[i]]
                else:
                    return False
                if node.flag:
                    if word[i + 1:] in word_set:
                        return True
                    else:
                        flag = search(tree, word[i + 1:])
                        if flag:
                            return True
            return False

        for word in words:
            if word:
                if search(tree, word):
                    out.append(word)
                node = tree
                for i in range(len(word)):
                    if word[i] in node.neighbors:
                        node = node.neighbors[word[i]]
                    else:
                        New_node = Node(word[i])
                        node.neighbors[word[i]] = New_node
                        node = New_node
                node.flag = 1
        return out


data = Solution()
words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
print(data.findAllConcatenatedWordsInADict(words))
words = ["cat", "cats", "catsdogcats", "dog"]
print(data.findAllConcatenatedWordsInADict(words))
words = ["a", "aa"]
print(data.findAllConcatenatedWordsInADict(words))
